package leetcode_acm.leetcode_1;

import leetcode_core.dataStruct.Hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月11日 12:44
 */
public class BuildTree2 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private Map<Integer,Integer> memo = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //1. 缓存{元素值=>下标}
        for (int i = 0; i < preorder.length; i++) {
            memo.put(inorder[i],i);
        }
        //2. 构建根节点
        return construct(preorder,0,preorder.length-1,inorder,0, inorder.length-1);
    }

    private TreeNode construct(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){
        //1. 判断是否越界
        if(preBegin > preEnd){
            return null;
        }
        //2. 计算下标
        //2.1 构建根节点
        int rootValIndex = memo.get(preorder[preBegin]);
        TreeNode root = new TreeNode(preorder[preBegin]);
        //2.2 计算左子树的in起始位置
        int leftInBegin = inBegin;
        //2.3 计算左子树的in结束位置
        int leftInEnd = rootValIndex-1;
        //2.4 计算右子树的in起始位置
        int rightInBegin = rootValIndex+1;
        //2.5 计算右子树的in的结束位置
        int rightInEnd = inEnd;
        //2.6 计算左子树的pre起始位置
        int leftPreBegin = preBegin+1;
        //2.7 计算左子树的pre的结束位置
        //计算左子树中有多少个元素
        int leftSize = rootValIndex-inBegin;
        int leftPreEnd = preBegin+leftSize;
        //2.8 计算右子树的pre起始位置
        int rightPreBegin = leftPreEnd+1;
        //2.9 计算右子树的pre结束位置
        int rightPreEnd = preEnd;
        //3. 构建左右子树节点
        root.left = construct(preorder,leftPreBegin,leftPreEnd,inorder,leftInBegin,leftInEnd);
        root.right = construct(preorder,rightPreBegin,rightPreEnd,inorder,rightInBegin,rightInEnd);
        return root;
    }
}
